What is kruskal's algorithm?

Kruskal's Algorithm

Kruskal's algorithm is a <a href="https://www.wikiwhat.page/kavramlar/greedy%20algorithm">greedy algorithm</a> used to find the <a href="https://www.wikiwhat.page/kavramlar/minimum%20spanning%20tree">minimum spanning tree</a> (MST) for a weighted, undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.

How it Works:

1. Initialization: Start with an empty forest of trees, where each vertex is a separate tree.

2. Edge Sorting: Sort all the edges of the graph in non-decreasing order of their weights.

3. Edge Iteration: Iterate through the sorted list of edges. For each edge:

   • Check if adding this edge to the current forest would create a <a href="https://www.wikiwhat.page/kavramlar/cycle">cycle</a>. This can be efficiently done using a <a href="https://www.wikiwhat.page/kavramlar/disjoint%20set%20union">disjoint-set union</a> (DSU) data structure. If the vertices connected by the edge are already in the same set (belong to the same tree), adding the edge would create a cycle.
   • If adding the edge doesn't create a cycle, then include the edge in the MST and merge the two trees that the edge connects into a single tree using the DSU structure's union operation.

4. Termination: Continue iterating until all vertices are connected into a single tree. This tree is the minimum spanning tree.

Key Concepts:

• Greedy Approach: Kruskal's algorithm makes the locally optimal choice at each step (choosing the lowest-weight edge that doesn't create a cycle) with the hope of finding a global optimum (the MST).
• Minimum Spanning Tree (MST): A spanning tree with the minimum possible total edge weight.
• Cycle Detection: Crucial for preventing the creation of cycles, typically achieved with the <a href="https://www.wikiwhat.page/kavramlar/disjoint%20set%20union">Disjoint-Set Union</a> data structure.
• Disjoint-Set Union (DSU): Maintains a collection of disjoint sets (trees in this case) and efficiently supports finding the set that an element belongs to and merging two sets into one.

Time Complexity:

The time complexity of Kruskal's algorithm is typically O(E log E) or O(E log V), where E is the number of edges and V is the number of vertices in the graph. This is primarily due to the sorting of the edges (O(E log E)) and the DSU operations (which can be made nearly constant time with appropriate optimizations like path compression and union by rank). Since E can be at most V², log E = O(log V), so O(E log E) is often written as O(E log V).